#include<bits/stdc++.h>
#include <cstring>
using namespace std;
#define maxn 101
struct node
{
    int a,b,w;
}e[maxn];
int m,n;
int cnt = 0;
int dis[maxn];
void add(int a,int b,int w)
{
    e[cnt].a = a;
    e[cnt].b = b;
    e[cnt++].w = w;
}

bool bf(int u)
{
    memset(dis, 0x3f3f3f3f,sizeof(dis));
    dis[u]=0;
    for(int i = 1;i < n;i++)
    {
        bool flag = false;
        for(int j = 0;j<m;j++)
        {
            if(dis[e[j].b]>dis[e[j].a]+e[j].w)
            {
                dis[e[j].b] = dis[e[j].a]+e[j].w;
                flag = true;
            }
        }
        if(!flag)
        {
            return false;
        }
    }
    for(int i = 0;i < m;i++)
    {
        if(dis[e[i].b]>dis[e[i].a]+e[i].w)
            {
                return true;
            }
    }
    return false;
}

void print()
{
    cout<<"输出源点到其他店的距离"<<endl;
    for(int i = 1;i <=n;i++)
    {
        cout<<dis[i]<<" ";
    }
}

int main()
{
    cin>>n>>m;
    for(int i = 0;i < m;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        add(a,b,w);
    }
    cout<<bf(1);
    print();
}